10044. LinkedList Merge
Merge two sorted linked lists and
return it as a new list. The new list should be made by splicing together the
nodes of the first two lists.
Definition of a single
linked list:
//Java
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
// C++
class ListNode
{
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
Implement function merge that merges two linked lists.
// Java
ListNode merge(ListNode l1, ListNode l2)
// C++
ListNode* merge(ListNode *l1, ListNode *l2)
Example
SOLUTION
linked list
Algorithm analysis
Let res be the pointer to the resulting linked list. To the end of res we’ll
assign the head of
either the first or the second list (the one that is smaller). If the first
list ends earlier, then we assign to res
what remains from the
second list. If the second list ends earlier, then we assign to res what remains from the first list.
Algorithm realization
ListNode* merge(ListNode *l1, ListNode *l2)
{
Create a fictitious vertex and set the pointer current to it.
ListNode* res = new ListNode(0);
ListNode* current = res;
while (true)
{
If the list l1 is finished, then we assign the second list l2 to the end of current.
if (l1 == NULL)
{
current->next = l2;
break;
}
If the list l2 is finished, then we assign the first list l1 to the
end of current.
if (l2 == NULL)
{
current->next = l1;
break;
}
If the value val
of the first list is less than the value val
of the second list, then the node of the first list is assigned to current.
if (l1->val < l2->val)
{
current->next = l1;
l1 = l1->next;
}
Otherwise, the node of the second list is assigned
to current.
else
{
current->next = l2;
l2 = l2->next;
}
Move forward the pointer current.
current =
current->next;
}
Return the answer, skipping the first fictitious vertex.
return res->next;
}
Java realization
ListNode merge(ListNode l1, ListNode l2)
{
ListNode res = new ListNode(0);
ListNode current = res;
while (true)
{
if (l1 == null)
{
current.next = l2;
break;
}
if (l2 == null)
{
current.next = l1;
break;
}
if (l1.val < l2.val)
{
current.next = l1;
l1 = l1.next;
}
else
{
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
return res.next;
}